package ua.yandex.collections;

import java.util.Comparator;

public class MyCollections {

    public static void reverse(MyList list) {
        Object[] array = list.toArray();
        for (int i = 0; i < array.length / 2; i++) {
            Object obj = array[i];
            array[i] = array[array.length - i - 1];
            array[array.length - i - 1] = obj;
        }
        list.clear();
        list.addAll(array);
    }

    private static int arrayBinarySearch(Object[] array,
            Object key,
            Comparator cp,
            int left,
            int right) {
        if (left == right) {
            if (cp.compare(key, array[left]) == 0) {
                return left;
            } else {
                if (cp.compare(key, array[left]) < 0) {
                    return -left - 1;
                } else {
                    return -left - 2;
                }
            }

        } else {
            int middle = left + (right - left) / 2;
            if (cp.compare(key, array[middle]) <= 0) {
                return arrayBinarySearch(array, key, cp, left, middle);
            } else {
                return arrayBinarySearch(array, key, cp, middle + 1, right);
            }
        }
    }

    static class DefaultComparator implements Comparator {

        @Override
        public int compare(Object a, Object b) {
            return ((Comparable) a).compareTo((Comparable) b);
        }
    }

    public static int binarySearch(MyList list, Object key) {
        Comparator cp = new DefaultComparator();
        return binarySearch(list, key, cp);
    }

    public static int binarySearch(MyList list, Object key, Comparator cp) {
        if (list.isEmpty()) {
            return -1;
        }
        Object[] array = list.toArray();
        return arrayBinarySearch(array, key, cp, 0, array.length - 1);
    }
}
